package demo2;

import demo1.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }
    Node root = null;
    //创建树
    public Node createTree() {
        Node n1 = new Node(11);
        Node n2 = new Node(21);
        Node n3 = new Node(31);
        Node n4 = new Node(41);
        Node n5 = new Node(51);
        Node n6 = new Node(61);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.right = n6;
        return n1;
    }
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        List<Integer> left = postorderTraversal(root.left);
        list.addAll(left);
        List<Integer> right = postorderTraversal(root.right);
        list.addAll(right);
        list.add(root.val);
        return list;
    }
    public void postorder(Node root) {
        if (root == null) {
            return;
        }
        postorder(root.left);
        postorder(root.right);
        list.add(root.val);
    }

    public List<Integer> inorderTraversal(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        List<Integer> left = inorderTraversal(root.left);
        list.addAll(left);
        list.add(root.val);
        List<Integer> right = inorderTraversal(root.right);
        list.addAll(right);
        return list;
    }
    public void inorder(Node root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }



    public List<Integer> preorderTraversal(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.add(root.val);
        List<Integer> left = preorderTraversal(root.left);
        list.addAll(left);
        List<Integer> right = preorderTraversal(root.right);
        list.addAll(right);

        return list;
    }
    public void pre(Node root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        pre(root.left);
        pre(root.right);
    }
    int count = 0;
    // 获取树中节点的个数
    int size(Node root) {
        preorder(root);
        return count;
    }
    public void preorder(Node root) {
        if (root == null) {
            return;
        }
        count++;
        preorder(root.left);
        preorder(root.right);
    }
    // 获取叶子节点的个数
    // 子问题思路-求叶子结点个数
    int getLeafNodeCount(Node root) {
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    // 获取第K层节点的个数
    int getKLevelNodeCount(Node root,int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
    }
    // 获取二叉树的高度
    int getHeight(Node root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.left);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
    // 检测值为value的元素是否存在
    Node find(Node root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        Node left = find(root.left,val);
        if (left != null) {
            return left;
        }
        Node right = find(root.right,val);
        if (right != null) {
            return right;
        }
        return null;
    }
    //层序遍历
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> lists = new LinkedList<>();
        Queue<Node> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new LinkedList<>();
            while (size-- > 0) {
                BinaryTree.Node node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(Node root) {
        Queue<Node> queue = new LinkedList<>();
        if (root == null) {
            return true;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            BinaryTree.Node node = queue.poll();
            if (node == null) {
                break;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }
}
